﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinarTtree.BuildTree2
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[] nums1 = new int[] { 3, 9, 20, 15, 7 };//前序
            int[] nums2 = new int[] { 9, 3, 15, 20, 7 };//中序
            TreeNode root = BuildTree(nums1, nums2);

            Left(root);
            Console.ReadKey();
        }
        public static void Left(TreeNode treeNode)
        {
            if (treeNode == null)
            {
                return;
            }
            Left(treeNode.left);
            Console.WriteLine(treeNode.val);
            Left(treeNode.right);
        }

        //递归：整体看待 
        public static TreeNode BuildTree(int[] preorder, int[] inorder)
        {
            return SetValue1(preorder, inorder, 0, preorder.Length - 1, 0, inorder.Length - 1);
        }
        public static TreeNode SetValue1(int[] preorder, int[] inorder, int prePre, int preLast, int inPre, int inLast)
        {
            if (prePre> preLast)
            {
                return null;
            }
            int rootValue = preorder[prePre];
            int rootIndex = 0;
            for (int i = 0; i < inorder.Length; i++)
            {
                if (inorder[i] == rootValue)
                {
                    rootIndex = i;
                    break;
                }
            }

            TreeNode root = new TreeNode(rootValue);
            root.right = SetValue1(preorder, inorder, prePre + (rootIndex - 1 - inPre+1) +1, preLast, rootIndex + 1, inLast);
            root.left = SetValue1(preorder, inorder, prePre+1, prePre + 1 + (rootIndex - 1 - inPre+1)-1, inPre, rootIndex-1);

            return root;
        }
    }
}
